package likou;

/**
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2020/11/26 09:58
 */
public class _164 {
    int maximumGapRes = Integer.MIN_VALUE;
    public int maximumGap(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return 0;
        }

        maximumGapLeftHelper(nums, 0, nums.length - 1,false,0);
        return maximumGapRes;
    }

    public int maximumGapLeftHelper(int[] nums, int start, int end,boolean isLeft,int lastIndex) {
        if (start < 0 || end >= nums.length || end <= start) {
            if (start >= 0 && start < nums.length) return nums[start];
            if (end >= 0 && end < nums.length) return nums[end];
            return lastIndex;
        }

        if (end == start + 1){
            maximumGapRes = Math.max(Math.abs(nums[start]-nums[end]) , maximumGapRes);
            if (isLeft){
                return Math.max(nums[start],nums[end]);
            }else{
                return Math.min(nums[start],nums[end]);
            }
        }

        int left = start, right = end, index = nums[left];
        int min = index, max = index;
        while (left < right) {
            while (left < right && nums[right] >= index) {
                max = Math.max(nums[right--],max);

            }
            while (left < right && nums[left] <= index) {
                min = Math.min(nums[left++],min);
            }
            max = Math.max(nums[left], max);
            min = Math.min(nums[right], min);
            if (left < right) {
                swap(nums, left, right);
            }
        }
        nums[start] = nums[left];
        nums[left] = index;

        maximumGapRes = Math.max(Math.max(index - maximumGapLeftHelper(nums, start, left - 1,true,index),
                maximumGapLeftHelper(nums,  left + 1, end,false,index)-index),maximumGapRes);

        if (isLeft){
            return max;
        }else{
            return min;
        }

    }

    private void swap(int[] nums, int index1, int index2) {
        int tmp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = tmp;
    }
}
